#ifndef RINGWALKER_H
#define RINGWALKER_H

#include <vcg/simplex/face/jumping_pos.h>
#include <vcg/complex/trimesh/allocate.h>
#include <vcg/complex/trimesh/update/flag.h>
#include <vector>
#include <set>

using namespace std;

template <class MeshType>
class RingWalker
{
public:

    typedef typename MeshType::FaceType   FaceType;
    typedef typename MeshType::VertexType VertexType;
    typedef typename MeshType::ScalarType ScalarType;
    typedef typename MeshType::FaceIterator FaceIterator;
    typedef typename MeshType::VertexIterator VertexIterator;
    typedef typename MeshType::CoordType CoordType;


    vector<VertexType*> allV;
    vector<FaceType*> allF;

    vector<VertexType*> lastV;
    vector<FaceType*> lastF;

    MeshType* m;

    RingWalker(VertexType* v, MeshType* m) : m(m)
    {
        assert((v - &*m->vert.begin()) < m->vert.size());
        //clearFlags();
        //lastF.clear();
        //lastV.clear();

        insertAndFlag(v);

    }

    void insertAndFlag1Ring(VertexType* v)
    {
        insertAndFlag(v);

        typename vcg::face::Pos<FaceType> p(v->VFp(),v);
        assert(p.V() == v);

        int count = 0;
        vcg::face::Pos<FaceType> ori = p;
        do
        {
            insertAndFlag(p.F());
            p.FlipF();
            p.FlipE();
            assert(count++ < 100);
        } while (ori != p);

    }

    void insertAndFlag(FaceType* f)
    {
        if (!f->IsV())
        {
            allF.push_back(f);
            lastF.push_back(f);
            f->SetV();
            insertAndFlag(f->V(0));
            insertAndFlag(f->V(1));
            insertAndFlag(f->V(2));
        }
    }

    void insertAndFlag(VertexType* v)
    {
        if (!v->IsV())
        {
            allV.push_back(v);
            lastV.push_back(v);
            v->SetV();
        }
    }


    static void clearFlags(MeshType* m)
    {
        vcg::tri::UpdateFlags<MeshType>::VertexClearV(*m);
        vcg::tri::UpdateFlags<MeshType>::FaceClearV(*m);
    }

    void clear()
    {
        for(int i=0; i< allV.size(); ++i)
            allV[i]->ClearV();
        for(int i=0; i< allF.size(); ++i)
            allF[i]->ClearV();

        allV.clear();
        allF.clear();
    }

    void expand()
    {
        //cerr << "Before " << lastV.size() << " " << lastF.size() << endl;
        vector<VertexType*> lastVtemp = lastV;

        lastV.clear();
        lastF.clear();

        for(typename vector<VertexType*>::iterator it = lastVtemp.begin(); it != lastVtemp.end(); ++it)
        {
            insertAndFlag1Ring(*it);
        }

        //cerr << "After " << lastV.size() << " " << lastF.size() << endl;
    }

    void expand(int k)
    {
        for(int i=0;i<k;++i)
            expand();
    }
};


#endif // RINGWALKER_H
